Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

  1. "1 + 1" = 2
  2. " 2-1 + 2 " = 3
  3. "(1+(4+5+2)-3)+(6+8)" = 23
  4. `

Note: Do not use the eval built-in library function.

Solution:

  1. public class Solution {
  2.   public int calculate(String s) {
  3.     char[] a = s.toCharArray();
  5.     Stack<Integer> stack = new Stack<Integer>();
  6.     stack.push(1);
  8.     int res = 0;
  9.     int sign = 1;
  11.     for (int i = 0; i < a.length; i++) {
  12.       if (a[i] == ')') {
  13.         stack.pop();
  14.       } else if (a[i] == '+') {
  15.         sign = 1;
  16.       } else if (a[i] == '-') {
  17.         sign = -1;
  18.       } else if (a[i] == '(') {
  19.         stack.push(stack.peek() * sign);
  20.         sign = 1;
  21.       } else if (Character.isDigit(a[i])) {
  22.         int tmp = a[i] - '0';
  24.         while (i + 1 < s.length() && Character.isDigit(a[i + 1]))
  25.           tmp = tmp * 10 + a[++i] - '0';
  27.         res += sign * stack.peek() * tmp;
  28.       }
  29.     }
  31.     return res;
  32.   }
  33. }